package com.abel.sort;

import java.util.LinkedHashMap;

/**
 * @author xiachao
 * @date 2019/3/9
 */
public class Main {
    /**
     * 冒泡排序
     * @param array
     * @return
     */
    public void popSort(int [] array){
        int len = array.length;
        for(int i=0;i<len-1;i++){
            for(int j=0;j<len-1-i;j++){
                if(array[j] > array[j+1]){
                    int t = array[j];
                    array[j] = array[j+1];
                    array[j+1] = t;
                }
            }
        }
    }

    /**
     * 选择排序
     * @param array
     */
    public void selectSort(int [] array){
        int len = array.length;
        for(int i=0;i<len;i++) {
            for (int j = i + 1; j < len; j++) {
                if (array[j] < array[i]) {
                    int t = array[i];
                    array[i] = array[j];
                    array[j] = t;
                }
            }
        }
    }

    public void quickSort(int [] array){

        sort(array, 0, array.length - 1);

    }

    public void sort(int [] array, int low, int high){
        if(low >= high){
            return;
        }
        int index = getMidIndex(array, low, high);
        sort(array, index + 1, high);
        sort(array, low, index -1);
    }

    public int getMidIndex(int [] array, int low, int high){
        int key = array[low];
        while(low < high){
            while(low < high && array[low] < key){ low++;}
            while(low < high && array[high] > key){ high--;}
            if(low < high){
                int tmp = array[low];
                array[low] = array[high];
                array[high] = tmp;
            }
        }
        return low;
    }


    public int binarySearch(int [] array, int target){

        int begin = 0;
        int end = array.length - 1;
        while(begin < end){
            int mid = (begin + end) / 2;
            if(array[mid] == target){
                return mid;
            }
            if(array[mid] < target){
                begin = mid;
            }else{
                end = mid;
            }
        }
        return -1;
    }

    public void heapSort(int [] array, int head, int end){
        int len = array.length;


    }

    public static void main(String[] args) {
        System.out.println("---");
        System.out.println((int)'h');
        int [] array = {15, 9, 8, 5, 6, 12, 2, 1};
        new Main().quickSort(array);
        for(int i : array){
            System.out.print(i+", ");
        }
    }

}
